//  https://leetcode-cn.com/problems/4sum
//  FourCountSum.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/27.
//  Copyright © 2019 XFB. All rights reserved.
//  四数之和

import Foundation

class FourCountSum {
    
    /**
     给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     注意：
     答案中不可以包含重复的四元组。
     示例：
     给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
     满足要求的四元组集合为：
     [
     [-1,  0, 0, 1],
     [-2, -1, 1, 2],
     [-2,  0, 0, 2]
     ]
     */
    
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {

        if nums.count < 4 {
            return []
        }
        
        var tuples = [[Int]]()
        var sortedNums = nums.sorted()
        
        for i in 0 ..< sortedNums.count - 3 {
            if i > 0 && sortedNums[i] == sortedNums[i - 1] {
                continue
            }

            
            for j in i + 1 ..< sortedNums.count - 2 {
                if j > i + 1 && sortedNums[j] == sortedNums[j - 1] {
                    continue
                }
                
                var left = j + 1
                var right = sortedNums.count - 1
                
                while left < right {
                    let sum = sortedNums[i] + sortedNums[j] + sortedNums[left] + sortedNums[right];
                    if sum == target {
                        var list = [Int]()
                        list.append(sortedNums[i])
                        list.append(sortedNums[j])
                        list.append(sortedNums[left])
                        list.append(sortedNums[right])
                        tuples.append(list)
                        
                        while left < right && sortedNums[left] == sortedNums[left + 1] {
                            left = left + 1
                        }
                        
                        while left < right && sortedNums[right] == sortedNums[right - 1] {
                            right = right - 1
                        }
                        
                        left = left + 1
                        right = right - 1
                        
                    } else if sum < target {
                        left = left + 1
                    } else if sum > target {
                        right = right - 1
                    }
                }
            }
        }
        
        return tuples        
    }
    
    
    ///
    func fourSum1(_ nums: [Int], _ target: Int) -> [[Int]] {

        
        let sortedNums = nums.sorted(by: <)
        
        var threeCountSum = 0
        var twoCountSum = 0
        var left = 0
        var right = 0
        var tuples = [[Int]]()
        
        guard sortedNums.count >= 4 else {
            return tuples
        }
        
        for i in 0 ..< sortedNums.count - 3 {
            guard i == 0 || nums[i] != nums[i - 1] else {
                continue
            }
            
            threeCountSum = target - sortedNums[i]
            
            for j in i + 1 ..< sortedNums.count - 2 {
                guard j == i + 1 || sortedNums[j] != sortedNums[j - 1] else {
                    continue
                }
                
                twoCountSum = threeCountSum - nums[j]
            
                left = j + 1
                right = sortedNums.count - 1
                
                while left < right {
                    if sortedNums[left] + sortedNums[right] == twoCountSum {
                        tuples.append([sortedNums[i], sortedNums[j], sortedNums[left], sortedNums[right]])
                        repeat {
                            left = left + 1
                        } while left < right && sortedNums[left] == sortedNums[left - 1]
                        repeat {
                            right = right - 1
                        } while left < right && sortedNums[right] == sortedNums[right + 1]
                        
                    } else if sortedNums[left] + sortedNums[right] < twoCountSum {
                        repeat {
                            left = left + 1
                        } while left < right && sortedNums[left] == sortedNums[left - 1]
                    } else {
                        repeat {
                            right = right - 1
                        } while left < right && sortedNums[right] == sortedNums[right + 1]
                    }
                }
            }
        }
        return tuples
    }
    
}
